import { ICompareFunction, defaultCompare, Compare } from "../../../../utils/Util.ts";

export class Sort<T> {
    /**
     * 排序算法
     * @param array 需要进行排序的数组
     * @param compareFn 比对函数
     */
    constructor(private array: T[] = [], private compareFn: ICompareFunction<T> = defaultCompare) {}

    // 冒泡排序
    bubbleSort(): void {
        // 获取数组长度
        const { length } = this.array;
        for (let i = 0; i < length; i++) {
            // 从数组的0号元素遍历到数组的倒数第2号元素，然后减去外层已经遍历的轮数
            for (let j = 0; j < length - 1 - i; j++) {
                // 如果j > j + 1位置的元素就交换他们两个元素的位置
                if (this.compareFn(this.array[j], this.array[j + 1]) === Compare.BIGGER_THAN) {
                    this.swap(this.array, j, j + 1);
                }
            }
        }
    }

    // 选择排序
    selectionSort(): void {
        const { length } = this.array;
        // 声明一个变量用于存储最小元素的位置
        let indexMin = 0;
        for (let i = 0; i < length; i++) {
            // 初始值为外层循环当前遍历到的位置i
            indexMin = i;
            for (let j = i; j < length; j++) {
                // 如果当前遍历到元素小于indexMin位置的元素，就将当前遍历到的位置j赋值给indexMin
                if (this.compareFn(this.array[indexMin], this.array[j]) === Compare.BIGGER_THAN) {
                    indexMin = j;
                }
            }
            if (i !== indexMin) {
                this.swap(this.array, i, indexMin);
            }
        }
    }

    // 插入排序
    insertionSort(array: T[] = this.array): void {
        const { length } = array;
        let temp;
        // 假设0号元素已经排好序，从1号元素开始遍历数组
        for (let i = 1; i < length; i++) {
            // 声明辅助变量存储当前i的位置以及其对应的值
            let j = i;
            temp = array[i];
            // j大于0且j-1位置的元素大于i号位置的元素就把j-1处的值移动到j处，最后j--
            while (j > 0 && this.compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) {
                array[j] = array[j - 1];
                j--;
            }
            // 将temp放到正确的位置
            array[j] = temp;
        }
    }

    // 归并排序
    mergeSort(array: T[] = this.array): T[] {
        if (array.length > 1) {
            const { length } = array;
            // 获取中间值
            const middle = Math.floor(length / 2);
            // 递归填充左右数组
            const left = this.mergeSort(array.slice(0, middle));
            const right = this.mergeSort(array.slice(middle, length));
            // 合并左右数组
            array = this.merge(left, right);
        }
        return array;
    }

    private merge(left: T[], right: T[]) {
        let i = 0;
        let j = 0;
        const result: T[] = [];
        while (i < left.length && j < right.length) {
            // 如果left[i] < right[j]将left[i]加进result中，随后i自增，否则把right[j]加进result中，随后j自增
            result.push(this.compareFn(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]);
        }
        // 将left或right数组的剩余项添加进result中
        return result.concat(i < left.length ? left.slice(i) : right.slice(j));
    }

    // 快速排序
    quickSort(): T[] {
        return this.quick(this.array, 0, this.array.length - 1);
    }

    /**
     *
     * @param array 待排序数组
     * @param left 左边界
     * @param right 右边界
     * @private
     */
    private quick(array: T[], left: number, right: number) {
        // 该变量用于将子数组分离为较小值数组和较大值数组
        let index;
        if (array.length > 1) {
            // 对给定子数组执行划分操作，得到正确的index
            index = this.partition(array, left, right);
            // 如果子数组存在较小值的元素，则对该数组重复这个过程
            if (left < index - 1) {
                this.quick(array, left, index - 1);
            }
            // 如果子数组存在较大值的元素，也对该数组重复这个过程
            if (index < right) {
                this.quick(array, index, right);
            }
        }
        return array;
    }

    // 划分函数
    private partition(array: T[], left: number, right: number): number {
        // 从数组中选择一个值做主元，此处选择数组的中间值
        const pivot = array[Math.floor((right + left) / 2)];
        // 创建数组引用，分别指向左边数组的第一个值和右边数组的第一个值
        let i = left;
        let j = right;

        // left指针和right指针没有相互交错，就执行划分操作
        while (i <= j) {
            // 移动left指针直至找到一个比主元大的元素
            while (this.compareFn(array[i], pivot) === Compare.LESS_THAN) {
                i++;
            }

            // 移动right指针直至找到一个比主元小的元素
            while (this.compareFn(array[j], pivot) === Compare.BIGGER_THAN) {
                j--;
            }

            // 当左指针指向的元素比主元大且右指针指向的元素比主元小，并且左指针索引没有右指针索引大时就交换i和j号元素的位置，随后移动两个指针
            if (i <= j) {
                this.swap(array, i, j);
                i++;
                j--;
            }
        }
        // 划分结束，返回左指针索引
        return i;
    }

    /**
     * 计数排序
     * 1. 找到要排序数组的最大值
     * 2. 以上一步找到的最大值+1为长度创建一个计数数组
     * 3. 遍历要排序的数组，以当前遍历到的元素为索引，寻找计数数组中对应的位置将其初始化为0，如果此处位置有相同元素的话就自增
     * 4. 遍历计数数组，判断当前遍历到的元素值是否大于0，如果大于0就取当前遍历到的索引，替换array中的元素
     * @param array 需要进行排序的数组
     */
    countingSort(array: number[]): number[] {
        // 待排序数组为空或只有一个元素则不用排序
        if (array.length < 2) {
            return array;
        }
        // 找到待排序数组中的最大值
        const maxValue = this.findMaxValue(array);

        // 创建计数数组，数组长度为待排序数组的最大值+1
        const counts = new Array(maxValue + 1);
        // 遍历待排序数组，为计数数组赋值
        array.forEach((element) => {
            // 以当前遍历到的元素值为索引将对应位置元素值初始化为0
            if (!counts[element]) {
                counts[element] = 0;
            }
            // 当前位置的值进行自增，顺便应对数组中有重复值的情况，有重复值时当前位置的值必定大于1
            counts[element]++;
        });

        // 声明一个变量用于数组最终排序
        let sortedIndex = 0;
        // 遍历计数数组，根据计数数组的元素位置对待排序数组进行排序
        counts.forEach((count, i) => {
            // 如果当前遍历到的元素值大于0，则执行替换操作进行排序
            while (count > 0) {
                // 将当前元素索引赋值给array的sortedIndex号元素，随后sortedIndex自增
                array[sortedIndex++] = i;
                // 当前元素值自减，如果其值大于1，证明此处有重复元素，那么我们就继续执行while循环
                count--;
            }
        });
        // 最后，排序完成，返回排序好的数组
        return array;
    }

    // 桶排序
    bucketSort(array: number[], bucketSize = 5): T[] | number[] {
        if (array.length < 2) {
            return array;
        }
        // 创建桶，对桶进行排序
        return this.sortBuckets(<[][]>this.createBuckets(array, bucketSize));
    }

    /**
     * 创建桶
     * @param array 待排序数组
     * @param bucketSize 桶大小，即每个桶里的元素数量
     *
     * @return 二维数组类型的桶
     */
    private createBuckets = (array: number[], bucketSize: number): number[][] => {
        // 计算数组最大值与最小值
        let minValue = array[0];
        let maxValue = array[0];
        for (let i = 1; i < array.length; i++) {
            if (array[i] < minValue) {
                minValue = array[i];
            } else if (array[i] > maxValue) {
                maxValue = array[i];
            }
        }

        // 计算需要的桶数量，公式为: 数组最大值与最小值的差值与桶大小进行除法运算
        const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
        // 用于存放桶的二维数组
        const buckets: number[][] = [];

        // 计算出桶数量后，初始化每个桶
        for (let i = 0; i < bucketCount; i++) {
            buckets[i] = [];
        }

        // 遍历数组，将每个元素分布到桶中
        for (let i = 0; i < array.length; i++) {
            // 计算需要将元素放到哪个桶中，公式为: 当前遍历到的元素值与数组的最小值的差值与桶大小进行除法运算
            const bucketIndex: number = Math.floor((array[i] - minValue) / bucketSize);
            // 将元素放进合适的桶中
            buckets[bucketIndex].push(array[i]);
        }
        // 将桶返回
        return buckets;
    };

    // 对每个桶进行排序
    private sortBuckets(buckets: T[][]): T[] {
        const sortedArray: T[] = [];
        for (let i = 0; i < buckets.length; i++) {
            if (buckets[i] != null) {
                // 调用插入排序
                this.insertionSort(buckets[i]);
                // 将排序好的桶取出来，放进sortedArray中
                sortedArray.push(...buckets[i]);
            }
        }
        return sortedArray;
    }

    /**
     * 基数排序
     * @param array 待排序数组
     * @param radixBase 10进制排序，基数为10
     */
    radixSort(array: number[], radixBase = 10): number[] {
        if (array.length < 2) {
            return array;
        }
        // 获取数组的最小值和最大值
        const minValue = this.findMinValue(array);
        const maxValue = this.findMaxValue(array);
        // 当前有效数字,默认会从最后一位有效数字开始排序
        let significantDigit = 1;

        /**
         * 计算有效位
         * 最大值和最小值的差与有效数字进行除法运算，其值大于等于1就代表还有待排序的有效位
         */
        while ((maxValue - minValue) / significantDigit >= 1) {
            // 以当前有效位为参数对数组进行排序
            array = this.countingSortForRadix(array, radixBase, significantDigit, minValue);
            // 当前有效数字乘以基数，继续执行while循环进行基数排序
            significantDigit *= radixBase;
        }
        return array;
    }

    /**
     * 基于有效位进行排序
     * @param array 待排序数组
     * @param radixBase 基数
     * @param significantDigit 有效位
     * @param minValue 待排序数组的最小值
     */
    private countingSortForRadix = (array: number[], radixBase: number, significantDigit: number, minValue: number) => {
        // 声明桶索引以及桶
        let bucketsIndex;
        const buckets = [];
        // 辅助数组，用于计数完成的值移动会原数组
        const aux = [];
        // 通过基数来初始化桶
        for (let i = 0; i < radixBase; i++) {
            buckets[i] = 0;
        }

        // 遍历待排序数组，基于有效位计算桶索引执行计数排序
        for (let i = 0; i < array.length; i++) {
            // 计算桶索引
            bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase);
            // 执行计数操作
            buckets[bucketsIndex]++;
        }

        // 计算累积结果得到正确的计数值
        for (let i = 1; i < radixBase; i++) {
            buckets[i] = buckets[i] + buckets[i - 1];
        }

        // 计数完成，将值移回原始数组中,用aux辅助数组来存储
        for (let i = array.length - 1; i >= 0; i--) {
            // 计算当前元素的桶索引
            bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase);
            // 对当前桶索引内的元素执行自减操作,得到其在数组中的正确的位置
            const index = --buckets[bucketsIndex];
            // 计算出索引后，在aux中的对应位置存储当前遍历到的元素
            aux[index] = array[i];
        }
        return aux;
    };

    // 寻找数组中的最大值
    private findMaxValue = (array: number[]): number => {
        let max: number = array[0];
        for (let i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }

        return max;
    };

    // 寻找数组中的最小值
    private findMinValue = (array: number[]) => {
        let min: number = array[0];
        for (let i = 0; i < array.length; i++) {
            if (array[i] < min) {
                min = array[i];
            }
        }

        return min;
    };

    /**
     * 交换数组元素位置
     * @param array 需要进行操作的数组
     * @param a 交换的位置
     * @param b 被交换的位置
     */
    private swap = (array: T[], a: number, b: number): void => {
        const temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    };
}
